﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problem3
{
    class Program
    {
        static List<Int64> primes = new List<Int64>(100000) { 2 };
        static void Main(string[] args)
        {
            Int64 max = 600851475143;
            //Int64 max = 13195;
            Int64 tempMax = max;
            
            Int64 result = 0;

            for (Int64 i = 3; i <= tempMax; i += 2)
            {
                if (IsPrime(i))
                {
                    primes.Add(i);
                    if (tempMax % i == 0)
                    {
                        tempMax = CalculateNewMax(tempMax);
                    }
                }
            }

            for (int i = primes.Count-1; i >= 0; i--)
            {
                if (max % primes[i] == 0)
                {
                    result = primes[i];
                    break;
                }

            }

            Console.WriteLine(result);
            Console.ReadKey();
        }

        private static long CalculateNewMax(Int64 tempMax)
        {
            for (int i = 0; i < primes.Count; i++)
            {
                if (tempMax % primes[i] == 0)
                    return CalculateNewMax(tempMax / primes[i]);
            }

            return tempMax;
        }

        private static bool IsPrime(Int64 n)
        {
            for (int i=0; i < primes.Count; i++)
            {
                if (n % primes[i] == 0)
                    return false;
            }

            return true;
        }
    }
}
